
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

import static java.lang.System.exit;

public class MyHeap {
    int[]elem;
    int usedSize;

    public MyHeap(int n) {
        this.elem = new int[n];
    }
    public MyHeap() {
        this.elem= new int[10];
    }
    public void initElem(int[]arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i]=arr[i];
            usedSize++;
        }
    }
    //大根堆
    public void createHeap() {
        //下标-1\2
        //下标==usedSize-1
        for (int i = (usedSize-1-1)/2; i >=0 ; i--) {
            shiftDown(i,usedSize);
        }
    }
    //向下调整
    public void shiftDown(int parent ,int len) {
        int child=parent*2+1;
       while (child<len) {
            int tmp=elem[parent];
            if(child+1<len&&elem[child]<elem[child+1]) {
                child++;
            }
            if(tmp<elem[child]) {
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }
        }

    }

/*    public static void main(String[] args) {
        int[] array = {12,56,32,67,10,19,4};
      // insertSort(array);
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }*/
/*    public static void main(String[] args) {
        MyHeap myHeap=new MyHeap();
        int arr[]={27,15,19,18,28,34,65,49,25,37};
        myHeap.initElem(arr);
        myHeap.createHeap();
       // myHeap.shiftDown(0,myHeap.usedSize);
        System.out.println(Arrays.toString(myHeap.elem));
    }*/
    public static void insertSort(int[] array) {
        int j=0;
        for (int i = 1; i <array.length ; i++) {
            int tmp=array[i];
            for ( j = i-1; j !=-1 ; j--) {
                if(array[j]>tmp) {
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            if(j==-1) {
                array[j+1]=tmp;
            }
        }
    }
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
//整体进行插入排序
        shell(array,1);
    }

    public static void shell(int[] array,int gap) {
        int j=0;
        for (int i = gap; i <array.length ; i++) {
            int tmp=array[i];
            for ( j = i-gap; j >=0 ; j-=gap) {
                if(array[j]>tmp) {
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
                array[j+gap]=tmp;
        }
    }
    public static void selectSort(int[] array) {
    //选择排序
        //记录最小值的下标
        int min=0;
        for (int i = 0; i < array.length; i++) {
            min=i;
            for (int j = i+1; j < array.length ; j++) {
                if(array[min]>array[j]) {
                    min=j;
                }
            }
            int tmp=array[i];
            array[i]=array[min];
            array[min]=tmp;
        }
    }
    private  void  shiftUp(int child) {
        //chile最后一个元素的下标
        //parent父节点
        int parent=(child-1)/2;
        while (child>0) {
            //如果子节点大于父节点
            if(elem[child]>elem[parent]) {
                swap(elem,child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public void offer(int val) {
        //判满
        if(isFull()) {
            elem=Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize++]=val;
        shiftUp(usedSize-1);
    }
    public boolean isFull() {
        return usedSize==elem.length;
    }

    public static void main(String[] args) {
        MyHeap myHeap=new MyHeap();
        int[] array={1,23,6,8,78,9,12,3,456,3};
       array= myHeap.HeapSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void main1(String[] args) {
        int[] array={1,23,6,8,78,9,12,3,456,3};
        MyHeap myHeap=new MyHeap();
        myHeap.initElem(array);
        myHeap.createHeap();
        myHeap.offer(65);
        System.out.println("=============");
        System.out.println(myHeap.pop());
        System.out.println("============");
    }
    public int[] HeapSort(int array[]) {
        //每次出头节点放到最后
        //从小到大,需要建立大根堆
        //初始化
        initElem(array);
        //建立大根堆
        createHeap();
        int size=array.length-1;
        while (size!=0) {
            //和最后一个下标交换
            swap(elem,0,size);
            shiftDown(0,size);
            size--;
        }
        return elem;

    }
    public void swap(int []elem,int x,int y) {
        int tmp=elem[x];
        elem[x]=elem[y];
        elem[y]=tmp;
    }
    public int pop() {
        //头出
        if(isEmpty()) {
            System.out.println("没有元素");
            exit(0);
        }
        int ret=elem[0];
     //   elem[0]=-1;
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
         return ret;
    }
    public boolean isEmpty() {
        return usedSize==0;
    }

}

class IntCmp implements Comparator<Integer> {

    /**
     *@Override
     *     public int compare(Integer o1, Integer o2) {
     *         return o1-o2;
     *     }
     * @param o1
     * @param o2
     * @return
     */
    //大根堆
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }

}
